package 单周赛.history;

import java.util.*;

/**
 *
 */
public class 第357场单周赛 {

    public static void main(String[] args) {

        第357场单周赛 impl = new 第357场单周赛();


        System.out.println(impl.maximumSafenessFactor2(Arrays.asList(
                Arrays.asList(0, 1, 1),
                Arrays.asList(0, 0, 0),
                Arrays.asList(0, 0, 0)
        )));

    }

    /**
     * 1，如果不存在一个相邻和 >= m 长度为 2 的子数组，那么 nums
     * 长度 > 2 时，最后总要剩下一个长度为 2 的子数组，一定不能
     * 满足条件
     * 2，如果存在相邻和 >= m 长度为 2 的子数组，那么可以一直往
     * 往旁边边缘分割，到最后只剩下这个相邻和 >= m 的子数组，
     * 例如：11221 m = 4 --> 1122 1 或 1 1221
     * 注意：如果 nums 的长度 = 1，返回 true，如果长度为 2，分割
     * 后两个子数组的长度 = 1 ，满足条件，返回 true
     */
    public boolean canSplitArray(List<Integer> nums, int m) {
        if (nums.size() <= 2) {
            return true;
        }

        for (int i = 1; i < nums.size(); i++) {
            if (nums.get(i) + nums.get(i - 1) >= m) {
                return true;
            }
        }

        return false;
    }

    private List<int[]> stoleList = new ArrayList<>();

    private int n;

    private int[][] cache;

    private boolean[][] visited;

    /**
     * 记忆化+回溯（超时）
     */
    public int maximumSafenessFactor(List<List<Integer>> grid) {
        n = grid.size();
        cache = new int[n][n];
        visited = new boolean[n][n];
        for (int[] ints : cache) {
            Arrays.fill(ints, Integer.MAX_VALUE);
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (grid.get(i).get(j) == 1) {
                    stoleList.add(new int[]{i, j});
                }
            }
        }
        return dfs(0, 0, Integer.MAX_VALUE);
    }

    private static int[][] direction = new int[][]{{-1, 0}, {1, 0}, {0, 1}, {0, -1}};

    // 代表从 [i][j] 出发，到达 [n-1][n-1] 的最大安全系数是多少，preSafe 是之前经过的安全系数
    // 当前的安全系数必须<=之前的安全系数
    private Integer dfs(int i, int j, int preSafe) {
        visited[i][j] = true;
        int curSafe = cache[i][j];
        if (curSafe == Integer.MAX_VALUE) {
            for (int[] stole : stoleList) {
                int x = stole[0];
                int y = stole[1];
                curSafe = Math.min(curSafe, Math.abs(i - x) + Math.abs(j - y));
            }
            cache[i][j] = curSafe;
        }

        curSafe = Math.min(curSafe, preSafe);
        if (i == n - 1 && j == n - 1) {
            return curSafe;
        }

        int ans = 0;
        for (int[] direct : direction) {
            int nextI = i + direct[0];
            int nextJ = j + direct[1];

            if (nextI >= 0 && nextI < n && nextJ >= 0 && nextJ < n &&
                    !visited[nextI][nextJ]) {
                ans = Math.max(ans, dfs(nextI, nextJ, curSafe));
                visited[nextI][nextJ] = false;
            }
        }
        return ans;
    }

    /**
     * 广度优先搜索+深度优先搜索+二分枚举答案
     * 二分的前提，安全系数越高，越不容易达成，可以先找到
     * 所有的小偷，多源 bfs 搜索枚举的安全系数层数，最后
     * 用 dfs 判断 [0][0] 能否到达 [n-1][n-1]
     */
    public int maximumSafenessFactor2(List<List<Integer>> grid) {
        int n = grid.size();
        List<int[]> stoles = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (grid.get(i).get(j) == 1) {
                    stoles.add(new int[]{i, j});
                }
            }
        }

        int maxSafe = 0;
        int left = 0, right = n - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (dfsIsSafe(bfsCollectStoles(stoles, mid, n), 0, 0, n)) {
                maxSafe = Math.max(maxSafe, mid);
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return maxSafe;
    }

    private boolean[][] bfsCollectStoles(List<int[]> stoles, int safeCnt, int n) {
        boolean[][] visited = new boolean[n][n];
        Deque<int[]> queue = new ArrayDeque<>();
        queue.addAll(stoles);
        while (safeCnt-- > 0) {
            int size = queue.size();
            while (size-- > 0) {
                int[] cur = queue.pollFirst();
                int i = cur[0], j = cur[1];
                visited[i][j] = true;
                for (int[] direct : direction) {
                    int nextI = i + direct[0];
                    int nextJ = j + direct[1];
                    if (nextI >= 0 && nextI < n && nextJ >= 0 && nextJ < n &&
                            !visited[nextI][nextJ]) {
                        queue.add(new int[]{nextI, nextJ});
                    }
                }
            }
        }

        return visited;
    }

    // 从 [i][j] 是否可以到达 [n-1][n-1]
    private boolean dfsIsSafe(boolean[][] visited, int i, int j, int n) {
        if (visited[i][j]) {
            return false;
        }
        if (i == n - 1 && j == n - 1) {
            return true;
        }
        visited[i][j] = true;

        boolean isSafe = false;
        for (int[] direct : direction) {
            int nextI = i + direct[0];
            int nextJ = j + direct[1];
            if (nextI >= 0 && nextI < n && nextJ >= 0 && nextJ < n &&
                    !visited[nextI][nextJ]) {
                isSafe = isSafe || dfsIsSafe(visited, nextI, nextJ, n);
            }
        }
        return isSafe;
    }

    /**
     * 广度优先搜索+深度优先搜索+二分枚举答案
     * 可以先广度优先搜索，标记每个格子的安全系数，二分
     * 枚举答案的时候，如果当前格子安全系数 > 枚举的答案
     * 那么可以通过
     */
    public int maximumSafenessFactor3(List<List<Integer>> grid) {
        int n = grid.size();
        List<int[]> stoles = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (grid.get(i).get(j) == 1) {
                    stoles.add(new int[]{i, j});
                }
            }
        }
        bfsMarkSafe(stoles, grid);

        int maxSafe = 0;
        int left = 0, right = n - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (dfsIsSafe(grid, mid, 0, 0, new boolean[n][n])) {
                maxSafe = Math.max(maxSafe, mid);
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return maxSafe;
    }

    private boolean dfsIsSafe(List<List<Integer>> grid, int targetSafe, int i, int j, boolean[][] visited) {
        int n = grid.size();
        if (grid.get(i).get(j) <= targetSafe) {
            return false;
        }
        if (i == n - 1 && j == n - 1) {
            return true;
        }
        visited[i][j] = true;
        boolean isSafe = false;
        for (int[] direct : direction) {
            int nextI = i + direct[0];
            int nextJ = j + direct[1];
            if (nextI >= 0 && nextI < n && nextJ >= 0 && nextJ < n &&
                    !visited[nextI][nextJ]) {
                isSafe = isSafe || dfsIsSafe(grid, targetSafe, nextI, nextJ, visited);
            }
        }
        return isSafe;
    }

    private void bfsMarkSafe(List<int[]> stoles, List<List<Integer>> grid) {
        int n = grid.size();
        Deque<int[]> queue = new ArrayDeque<>();
        queue.addAll(stoles);
        int curSafe = 2;
        while (!queue.isEmpty()) {
            int size = queue.size();
            while (size-- > 0) {
                int[] cur = queue.pollFirst();
                for (int[] direct : direction) {
                    int nextI = cur[0] + direct[0];
                    int nextJ = cur[1] + direct[1];
                    if (nextI >= 0 && nextI < this.n && nextJ >= 0 && nextJ < this.n &&
                            grid.get(nextI).get(nextJ) == 0) {
                        grid.get(nextI).set(nextJ, curSafe);
                        queue.addLast(new int[]{nextI, nextJ});
                    }
                }
            }
            curSafe++;
        }
    }
}
